package algorithm.swordoff;

import java.util.Comparator;

/**
 * 把数组排成最小的数
 *
 * K神思路:基于快排的自定义排序
 */

public class SQ45 {
    public String minNumber(int[] nums) {
        // 直接用整数的比较会溢出,用字符串的比较
        Comparator<Integer> myComparator = (o1, o2) -> (o1.toString()+o2.toString()).compareTo(o2.toString()+o1.toString());
        myQuickSort(nums, 0, nums.length-1, myComparator);
        StringBuilder sb = new StringBuilder();
        for (int num : nums) sb.append(num);
        return sb.toString();
    }

    private void myQuickSort(int[] arr, int begin, int end, Comparator<Integer> comparator) {
        if (begin < end) {
            int pivot = findPivot(arr, begin, end, comparator);
            myQuickSort(arr, begin, pivot-1, comparator);
            myQuickSort(arr, pivot+1, end, comparator);
        }
    }

    private int findPivot(int[] arr, int begin, int end, Comparator<Integer> comparator) {
        while (begin < end) {
            while (begin < end && comparator.compare(arr[begin], arr[end]) <= 0) end--;
            mySwap(arr, begin, end);
            while (begin < end && comparator.compare(arr[begin], arr[end]) <= 0) begin++;
            mySwap(arr, begin, end);
        }
        return begin;
    }

    private void mySwap(int[] arr, int a, int b) {
        int temp = arr[a];
        arr[a] = arr[b];
        arr[b] = temp;
    }

    public static void main(String[] args) {
        SQ45 sq45 = new SQ45();
        System.out.println(sq45.minNumber(new int[]{999999998,999999997,999999999}));
    }
}
